#include <stdio.h>
#include <time.h>

int isPrime(int n) //传统的判断一个素数方法
{
    if (n <= 1)
    {
        return 0;
    }

    for (int i = 2; i < n; i++)
    {
        if (n % i == 0)
        {
            return 0;
        }
    }

    return 1;
}

int isPrimeImproved(int n) //改进方法判断素数
{
    if (n <= 1)
    {
        return 0;
    }

    if (n == 2 || n == 3)
    {
        return 0;
    }

    if (n % 2 == 0 || n % 3 == 0)
    {
        return 0;
    }

    int i = 5;
    int w = 2;

    while (i * i <= n)
    {
        if (n % i == 0)
        {
            return 0;
        }
        i += w;
        w = 6 - w;
    }

    return 1;
}

// 统计1~n的素数个数，并返回求解时间（传统方法）
int primeTimel(int n)
{
    int count = 0;

    for (int i = 1; i <= n; i++)
    {
        if (isPrime(i) == 1)
        {
            count++;
        }
    }

    return count;
}

// 统计1~n的素数个数，并返回求解时间(改进方法)
int primeTime2(int n)
{
    int count = 0;

    for (int i = 1; i <= n; i++)
    {
        if (isPrimeImproved(i) == 1)
        {
            count++;
        }
    }

    return count;
}

int main()
{

    int n;
    printf("请输入一个正整数：\n");
    scanf("%d", &n);
    clock_t start, end;
    double cpu_time_used;

    // 方法1求解时间和结果
    start = clock();
    int count1 = primeTimel(n);
    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("方法1求解结果：%d\n", count1);
    printf("方法1求解时间：%lf秒\n", cpu_time_used);

    // 方法2求解时间和结果
    start = clock();
    int count2 = primeTime2(n);
    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("方法2求解结果：%d\n", count2);
    printf("方法2求解时间：%lf秒\n", cpu_time_used);
    return 0;
}

//请输入一个正整数：
// 100000
//方法1求解结果：9592
//方法1求解时间：0.598000秒
//方法2求解结果：9590
//方法2求解时间：0.008000秒

//可见，当n足够大的时候方法2的效率远高于方法1